package leetcode.栈队列堆;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的前序遍历
 *
 * 分为递归遍历和非递归遍历
 *
 * 非递归需要用到栈
 *
 * 当然还有一种神操作：线索二叉树
 */
public class Test144二叉树的前序遍历 {


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 递归遍历
    public static List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> ans = new LinkedList<>();
       recursion(root, ans);
       return ans;
    }

    public static void recursion(TreeNode root, List<Integer> ans) {
        if (root == null)
            return;

        ans.add(root.val);
        recursion(root.left, ans);
        recursion(root.right, ans);
    }


    // 非递归遍历。需要用到 stack 来保存上一个节点
    public static List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 先一直把左节点全部输出
            while (root != null) {
                ans.add(root.val);
                stack.push(root);
                root = root.left;
            }
            // 然后恢复上层节点
            if (!stack.isEmpty()) {
                root = stack.pop();
                root = root.right;
            }
        }
        return ans;
    }

    public static void main(String[] args) {

    }
}
